package org.labuladong.经典贪心算法;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-22:52
 * @Description: 贪⼼算法可以认为是动态规划算法的⼀个特例，相⽐动
 * 态规划，使⽤贪⼼算法需要满⾜更多的条件（贪⼼选择性质），但是效率⽐
 * 动态规划要⾼
 *
 * ：每⼀步都做出⼀个局部最优的选择，最终的结果就是全局最优。
 *
 * ⼤部分问题明显不具有贪⼼选择性质。⽐如打⽃地主，对⼿出对⼉三，按照贪⼼策略，你应该出尽可能⼩的牌刚好压制住对⽅，但现实情况我们甚⾄可能会出王炸。这种情况就不能⽤贪⼼算法，⽽得使⽤动态规划解决，参⻅前⽂「动态规划解决博弈问题」。
 * @version: 1.0
 */

import java.util.Arrays;

/**
 * 请你设计⼀个算法，算出这些区间中最多有⼏个互不相交的区间。
 *
 * 输入：[[1,2], [2,3], [3,4], [1,3]]
 *
 * //排序
 * [[1,2], [1,3], [2,3], [3,4]]
 *
 * 你今天最多能参加⼏个活动呢？
 *
 * 435. 无重叠区间 是本道题目的变种（换一种问法），只要结果修改一下：return n - count;// 返回最多活动数
 */
public class 贪心算法之区间调度问题 {

	public static int maxActivities(int[][] intervals) {
		int n = intervals.length;
		if(n == 0) return 0;

		// 根据区间的结束时间进行排序
		Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

		/**
		 * //TODO 使用 Comparator.comparingInt 方法时，Java 内部会处理可能的整数溢出问题
		 * Comparator.comparingInt(a -> a[1]) 定义了排序的逻辑：根据每个区间的结束时间（a[1]）进行比较。
		 * 如果一个区间的结束时间小于另一个区间的结束时间，它会被排在前面。
		 * 如果两个区间的结束时间相同，它们的相对顺序会保持不变（因为 Comparator         是稳定的）。
		 * {{1, 2}, {2, 3}, {1, 4}, {3, 5}}
		 */

		int count = 1;// 初始化，至少有一个区间
		int end = intervals[0][1];// 初始化，第一个区间的结束时间
		for(int i = 1; i < n; i++) {
			// 如果当前区间的开始时间大于等于结束时间，则该区间可以加入
			if(intervals[i][0] >= end) {
				count++;
				// 更新结束时间为当前区间的结束时间
				end = intervals[i][1];
			}
		}
		return count;// 返回最多活动数

	}

	public static void main(String[] args) {
		int[][] intervals = {{1,2}, {2,3}, {3,4}, {1,3},{3,5},{4,6}};
		System.out.println(maxActivities(intervals));
	}
}
